import java.util.*;

/**
 * @Description: LeetCode每日练习
 * @Author: zhanglinxin
 * @CreateTime: 2025-03-01
 * @Version: 1.0
 */
public class Solution202503 {
    /**
     * @Description: 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
     * <p>
     * 示例 1：
     * 输入：s = "aab"
     * 输出：[["a","a","b"],["aa","b"]]
     * <p>
     * 示例 2：
     * 输入：s = "a"
     * 输出：[["a"]]
     * <p>
     * 提示：
     * 1 <= s.length <= 16
     * s 仅由小写英文字母组成
     * @param: [java.lang.String]
     * @return: java.util.List<java.util.List < java.lang.String>>
     * @Author: zhanglinxin
     * @date: 2025/3/1 14:51
     */
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i + 1));
                backtrack(s, i + 1, path, result);
                path.removeLast();
            }
        }
    }

    // 判断是否为回文字符串
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }

    /**
     * @Description: 给你一个由小写字母组成的字符串 s，和一个整数 k。
     * 请你按下面的要求分割字符串：
     * 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
     * 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
     * 请返回以这种方式分割字符串所需修改的最少字符数。
     * <p>
     * 示例 1：
     * 输入：s = "abc", k = 2
     * 输出：1
     * 解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
     * <p>
     * 示例 2：
     * 输入：s = "aabbc", k = 3
     * 输出：0
     * 解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
     * <p>
     * 示例 3：
     * 输入：s = "leetcode", k = 8
     * 输出：0
     * <p>
     * 提示：
     * 1 <= k <= s.length <= 100
     * s 中只含有小写英文字母。
     * @param: [java.lang.String, int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/3/3 07:59
     */
    public int palindromePartition(String s, int k) {
        int n = s.length();
        // cost[i][j] 表示将子串 s.substring(i, j + 1) 变为回文需要修改的字符数
        int[][] cost = new int[n][n];
        // 计算任意子串转换为回文所需修改的字符数
        for (int len = 2; len <= n; len++) {
            // 遍历所有可能的子串长度
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {
                // 如果两端字符相同，则无需修改，否则需要一次修改
                cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
            }
        }

        // dp[i][j] 表示将前i个字符分成j个部分所需的最小修改次数
        int[][] dp = new int[n + 1][k + 1];
        // 初始化dp数组，设置为一个较大的值表示尚未计算的状态
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 设置为字符串的最大长度作为初始值
                dp[i][j] = n;
            }
        }
        // 没有字符且不分割的情况
        dp[0][0] = 0;

        // 动态规划填充dp数组
        for (int i = 1; i <= n; i++) {
            // 遍历到第i个字符
            for (int j = 1; j <= k; j++) {
                // 分割成j个部分
                for (int m = i - 1; m >= 0; m--) {
                    // 尝试从前m个字符分割
                    // 更新dp[i][j]，考虑将前m个字符分成j-1部分，并把剩余部分变为回文的成本
                    dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + cost[m][i - 1]);
                }
            }
        }

        // 返回将整个字符串分成k个部分所需的最少修改次数
        return dp[n][k];
    }

    /**
     * @Description: 给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
     * 当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
     * <p>
     * 示例 1：
     * 输入：s = "abcbdd"
     * 输出：true
     * 解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
     * <p>
     * 示例 2：
     * 输入：s = "bcbddxy"
     * 输出：false
     * 解释：s 没办法被分割成 3 个回文子字符串。
     * <p>
     * 提示：
     * 3 <= s.length <= 2000
     * s只包含小写英文字母。
     * @param: [java.lang.String]
     * @return: boolean
     * @Author: zhanglinxin
     * @date: 2025/3/4 07:52
     */
    public boolean checkPartitioning(String s) {
        int n = s.length();
        if (n < 3) {
            return false;
        }
        // dp[i][j] 表示 s[i..j] 是否为回文串
        boolean[][] dp = new boolean[n][n];
        // 初始化dp数组,当子串长度为1时一定是回文
        for (int len = 1; len < n; len++) {
            // 遍历所有可能的子串长度
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {
                if (len == 1) {
                    dp[i][j] = true;
                } else {
                    boolean b = s.charAt(i) == s.charAt(j);
                    if (len == 2) {
                        dp[i][j] = b;
                    } else {
                        // 如果两端字符相同，则判断中间部分是否为回文串
                        dp[i][j] = dp[i + 1][j - 1] && b;
                    }
                }
            }
        }
        // 判断pd是否存在三个连续的ture
        for (int i = 0; i < n - 2; i++) {
            if (dp[0][i]) {
                for (int j = i + 1; j < n - 1; j++) {
                    if (dp[i + 1][j] && dp[j + 1][n - 1]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean checkPartitioning2(String s) {
        int len = s.length();
        char[] ch = s.toCharArray();
        // 动态规划数组，用于记录前i个字符能否被划分为特定数量的回文子串
        int[] dp = new int[len + 1];
        // 初始化dp数组的第一个元素，表示没有字符时（即空字符串）视为一种有效的划分方式
        dp[0] = 0x01;

        // 遍历每个字符作为中心点尝试扩展回文子串
        for (int i = 0; i < len; i++) {
            // 对于每个字符，尝试以当前字符为中心或当前字符与下一个字符之间的间隔为中心扩展回文
            for (int l : new int[]{i - 1, i}) {
                // 初始化右边界为当前字符位置
                int r = i;
                // 当l和r在合法范围内，并且左右两边字符相等时，继续向外扩展
                while (l >= 0 && r < len && ch[l] == ch[r]) {
                    // 使用位运算更新dp数组，记录当前能够形成多少段回文子串
                    // 每找到一个新的回文子串，就将dp中对应的位置标记出来
                    dp[r + 1] |= dp[l] << 1;
                    l--;  // 向左扩展
                    r++;  // 向右扩展
                }
            }
        }

        // 检查整个字符串是否能被分成3个回文子串
        // 通过检查dp[len]的第3位（从最低位开始计数）是否为1来判断
        return (dp[len] & 0x08) == 0x08;
    }

    /**
     * @Description: 给你一个由小写英文字母组成的回文字符串 palindrome ，
     * 请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。
     * 请你返回结果字符串。如果无法做到，则返回一个 空串 。
     * 如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：
     * 在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，
     * 因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。
     * <p>
     * 示例 1：
     * 输入：palindrome = "abccba"
     * 输出："aaccba"
     * 解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
     * 在所有方法中，"aaccba" 的字典序最小。
     * <p>
     * 示例 2：
     * 输入：palindrome = "a"
     * 输出：""
     * 解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。
     * <p>
     * 提示：
     * 1 <= palindrome.length <= 1000
     * palindrome 只包含小写英文字母。
     * @param: [java.lang.String]
     * @return: java.lang.String
     * @Author: zhanglinxin
     * @date: 2025/3/5 07:55
     */
    public String breakPalindrome(String palindrome) {
        int len = palindrome.length();
        if (len == 1) {
            return "";
        }
        char[] ch = palindrome.toCharArray();
        boolean f = true;
        for (int i = 0; i < len; i++) {
            if (ch[i] != 'a') {
                ch[i] = 'a';
                f = false;
            }
            if (f && i == len - 1 && ch[i] != 'b') {
                ch[i] = 'b';
            }
            if (isPalindrome(new String(ch))) {
                ch = palindrome.toCharArray();
                f = true;
                continue;
            }
            return new String(ch);
        }
        return "";
    }

    // 判断是否为回文字符串
    private boolean isPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }

    public String breakPalindrome2(String palindrome) {
        int n = palindrome.length();
        if (n == 1) {
            return "";
        }
        char[] data = palindrome.toCharArray();
        for (int i = 0; i * 2 + 1 < n; i++) {
            if (data[i] != 'a') {
                data[i] = 'a';
                return new String(data);
            }
        }
        data[n - 1] = 'b';
        return new String(data);
    }

    /**
     * @Description: 给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
     * 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
     * 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
     * 将 nums[i] 和 nums[j] 都减去 2^k 。
     * 如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
     * 请你返回数组 nums 中 美丽子数组 的数目。
     * 子数组是一个数组中一段连续 非空 的元素序列。
     * <p>
     * 示例 1：
     * 输入：nums = [4,3,1,2,4]
     * 输出：2
     * 解释：nums 中有 2 个美丽子数组：[3,1,2] 和 [4,3,1,2,4] 。
     * - 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
     * - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 2^1 ，子数组变成 [1, 1, 0] 。
     * - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 2^0 ，子数组变成 [0, 0, 0] 。
     * - 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
     * - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 2^2 ，子数组变成 [0, 3, 1, 2, 0] 。
     * - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 2^0 ，子数组变成 [0, 2, 0, 2, 0] 。
     * - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 2^1 ，子数组变成 [0, 0, 0, 0, 0] 。
     * <p>
     * 示例 2：
     * 输入：nums = [1,10,4]
     * 输出：0
     * 解释：nums 中没有任何美丽子数组。
     * @param: [int[]]
     * @return: long
     * @Author: zhanglinxin
     * @date: 2025/3/6 07:58
     */
    public long beautifulSubarrays(int[] nums) {
        //  由于每次操作中需要从子数组中选择两个不同的数分别减去 2^k,使得子数组中所有元素均变为 0，由此可知对于子数组中所有元素 2^k
        //  出现的次数之和必须是偶数。换一种说法，即对于二进制中第 i 位，则数组中所有元素第 i 位为 1 的数目一定为偶数，
        //  则此时满足数组中所有元素第 i 位的异或和一定为 0。即对所有元素做异或操作，其值为0.
        //  由此可知，对于数组中所有元素异或和为0的子数组，一定满足题目要求，因此问题转化为求异或和为0的子数组个数。
        //  已知前i个元素的异或值为x，前j个元素的异或值为y，如果nums[i……j]是美丽子数组，那么x和y必然相等
        Map<Integer, Integer> cnt = new HashMap<>();
        // cur记录当前异或和，ans记录满足条件的子数组个数
        int cur = 0, ans = 0;
        // 异或值为0，
        cnt.put(0, 1);
        for (int x : nums) {
            // 求前n位异或值
            cur ^= x;
            // 获取之前异或和为cur的子数组个数,并累加到ans中
            ans += cnt.getOrDefault(cur, 0);
            cnt.put(cur, cnt.getOrDefault(cur, 0) + 1);
        }
        return ans;
    }

    /**
     * @Description: 给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
     * 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
     * 返回数组 nums 中 非空 且 美丽 的子集数目。
     * nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。
     * 只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
     * <p>
     * 示例 1：
     * 输入：nums = [2,4,6], k = 2
     * 输出：4
     * 解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
     * 可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
     * <p>
     * 示例 2：
     * 输入：nums = [1], k = 1
     * 输出：1
     * 解释：数组 nums 中的美丽数组有：[1] 。
     * 可以证明数组 [1] 中只存在 1 个美丽子集。
     * <p>
     * 提示：
     * 1 <= nums.length <= 18
     * 1 <= nums[i], k <= 1000
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/3/7 07:57
     */
    public int beautifulSubsets(int[] nums, int k) {
        // 创建一个哈希表groups，键为nums数组中元素模k的结果，值为另一个映射（TreeMap），
        // 这个映射记录了每个余数对应的具体数值及其出现次数。
        Map<Integer, Map<Integer, Integer>> groups = new HashMap<>();

        // 遍历nums数组中的每一个元素a，将其分组到groups中对应的模k结果下，
        // 并更新或添加其在所属组内的计数。
        for (int a : nums) {
            groups.computeIfAbsent(a % k, key -> new TreeMap<>()).merge(a, 1, Integer::sum);
        }
        // 初始化答案变量ans为1，后续用于存储所有可能美丽子集数量的乘积。
        int ans = 1;
        // 遍历groups哈希表中的每一个条目（即每个模k分组）。
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : groups.entrySet()) {
            // 获取当前分组内的元素及其次数映射g。
            Map<Integer, Integer> g = entry.getValue();
            // 获取当前分组内不同元素的数量m。
            int m = g.size();
            // 创建一个二维数组f，用于动态规划计算当前分组内美丽子集的数量。
            // f[i][0]表示不选择第i个元素时的美丽子集数目，f[i][1]表示选择第i个元素时的美丽子集数目。
            int[][] f = new int[m][2];
            // 初始化第一个元素的选择状态。
            // 不选第一个元素时，美丽子集数目为1（空集）。
            f[0][0] = 1;
            // 选第一个元素时，美丽子集数目为其所有组合减去1。
            f[0][1] = (1 << g.get(g.keySet().iterator().next())) - 1;
            // 初始化迭代器和其他辅助变量，准备遍历当前分组内的元素。
            int i = 1;
            Iterator<Map.Entry<Integer, Integer>> it = g.entrySet().iterator();
            // 前一个元素
            Map.Entry<Integer, Integer> prev = it.next();
            // 遍历当前分组内的其余元素。
            while (it.hasNext()) {
                // 当前元素
                Map.Entry<Integer, Integer> curr = it.next();
                // 更新不选择当前元素时的美丽子集数目。
                f[i][0] = f[i - 1][0] + f[i - 1][1];
                // 根据当前元素与前一个元素的差值是否为k，更新选择当前元素时的美丽子集数目。
                if (curr.getKey() - prev.getKey() == k) {
                    f[i][1] = f[i - 1][0] * ((1 << curr.getValue()) - 1);
                } else {
                    f[i][1] = (f[i - 1][0] + f[i - 1][1]) * ((1 << curr.getValue()) - 1);
                }
                // 更新prev为当前元素，准备处理下一个元素。
                prev = curr;
                i++;
            }
            // 将当前分组内所有美丽子集的总数目累乘到答案变量ans中。
            ans *= f[m - 1][0] + f[m - 1][1];
        }
        // 返回美丽子集的总数目，减去1是因为要排除掉空集的情况。
        return ans - 1;
    }


    public static void main(String[] args) {
        Solution202503 solution202503 = new Solution202503();
        boolean b = solution202503.checkPartitioning("bcbddxy");
        String s = solution202503.breakPalindrome("aba");
        System.out.println(s);
    }

}
